package com.java.linkedlist;

/**
 * 约瑟夫问题
 * 环形链表
 */
public class Josepfu {

    public static void main(String[] args) {

        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //加入5个节点
        circleSingleLinkedList.addBoy(5);

        //显示
        circleSingleLinkedList.showBoy();

        /**
         * 根据用户的输入，生成一个节点出圈的顺序
         *
         *
         */
        circleSingleLinkedList.countBoy(1,2,5);


    }

}

class CircleSingleLinkedList{

    //创建一个first节点，当前没有编号
    private Boy first = null;

    //添加节点，构建成一个环形的链表
    public void addBoy(int nums){
        //做一个数据校验
        if (nums < 1){
            System.out.println("数据不正确");
            return;
        }

        Boy curBoy = null; //辅助指针，帮助构建环形链表
        //使用一个for循环创建一个环形链表
        for (int i=0; i<=nums ; i++){
            //根据编号创建节点
            Boy boy = new Boy(i);
            //如果是第一个节点
            if (i == 1){
                first = boy;
                first.setNext(first); //构成一个环
                curBoy = first;//让curBoy指向第一个节点
            }else {
                if (curBoy != null) {
                    curBoy.setNext(boy); //上一个节点指向添加进来的节点
                }
                boy.setNext(first); //构成环形，指向第一个节点
                curBoy = boy; //可能后面还有数据添加
            }
        }
    }

    //遍历当前的环形链表
    public void showBoy(){
        //判断是否为空
        if (first == null){
            System.out.println("链表为空，没有节点");
            return;
        }
        //有，因为first不能动，所以使用辅助指针
        Boy curBoy = first;
        while (true){
            System.out.println("节点的编号："+curBoy.getNo());
            if (curBoy.getNext() == first){
                //遍历完毕
                break;
            }
            curBoy = curBoy.getNext(); //后移查找
        }
    }


    //根据用户的输入，计算出节点出圈的顺序

    /**
     *
     * @param startNo 表示从第几个节点开始数
     * @param countNum 表示数几下
     * @param nums 表示由多少个节点数在题中
     */
    public void countBoy(int startNo, int countNum , int nums){
        //先对数据进行校验
        if (first == null || startNo <1 || startNo > nums){
            System.out.println("参数输入有误");
            return;
        }
        //创建辅助指针
        Boy helper = first;

        //事先将辅助指针指向环形链表的最后这个节点
        while (true){
            if (helper.getNext() == first){ //说明helper指向了最后节点
                break;
            }
            helper = helper.getNext();
        }

        //报数前，先让first 和 helper 移动到startNo上
        for (int j = 0 ; j<startNo-1 ; j++){
            first = first.getNext();
            helper = helper.getNext();
        }

        //报数时，让first 和 helper 移动到 countNum-1，然后出圈
        while (true){
            //表示只有一个节点
            if (helper == first){
                break;
            }
            //让first 和 helper 移动到 countNum-1次
            for (int j=0 ; j<countNum-1 ; j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时，first指向的节点，就是要出圈的节点
            System.out.println("节点出圈的编号为："+first.getNo());
            //将first指向的节点出圈
            first = first.getNext(); //
            helper.setNext(first);
        }
        System.out.println("最后留在链表中的节点为:"+helper.getNo());


    }





}


class Boy{

    private int no;
    private Boy next;

    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
